#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    /**
     * @brief O(m*n)
     *
     * @param grid
     * @return int
     */
    int countNegatives(vector<vector<int>> &grid)
    {
        int m = grid.size(), n = grid[0].size();
        int count = 0;
        for (size_t i = 0; i < m; i++)
        {
            for (size_t j = 0; j < n; j++)
            {
                if (grid[i][j] < 0)
                {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * @brief
     *
     * @param grid
     * @return int
     */
    int countNegatives_2(vector<vector<int>> &grid)
    {
        int num = 0;
        for (auto x : grid)
        {
            int l = 0, r = (int)x.size() - 1, pos = -1;
            while (l <= r)
            {
                int mid = l + ((r - l) >> 1);
                if (x[mid] < 0)
                {
                    pos = mid;
                    r = mid - 1;
                }
                else
                    l = mid + 1;
            }
            if (~pos)
                num += x.size() - pos; // pos=-1表示这一行全是>=0的数，不能统计
        }
        return num;
    }

    int countNegatives_3(vector<vector<int>> &grid)
    {
        auto solve = [](int l, int r, int L, int R, vector<vector<int>> grid) -> int
        {
            if (l > r)
                return 0;
            int mid = l + ((r - l) >> 1), pos = -1;
            for (int i = L; i <= R; ++i)
            {
                if (grid[mid][i] < 0)
                {
                    pos = i;
                    break;
                }
            }
            int ans = 0;
            if (~pos)
            {
                ans += (int)grid[0].size() - pos;
                ans += solve(l, mid - 1, pos, R, grid);
                ans += solve(mid + 1, r, L, pos, grid);
            }
            else
            { // 说明[l..o-1]不会有负数，不用再去递归
                ans += solve(mid + 1, r, L, R, grid);
            }
            return ans;
        };
        return solve(0, (int)grid.size() - 1, 0, (int)grid[0].size() - 1, grid);
    }
    int countNegatives_4(vector<vector<int>> &grid)
    {
        int num = 0, m = (int)grid[0].size(), pos = (int)grid[0].size() - 1;
        for (auto x : grid)
        {
            int i;
            for (i = pos; i >= 0; --i)
            {
                if (x[i] >= 0)
                {
                    if (i + 1 < m)
                    {
                        pos = i + 1;
                        num += m - pos;
                    }
                    break;
                }
            }
            if (i == -1)
            {
                num += m;
                pos = -1;
            }
        }
        return num;
    }
};
int main()
{
    Solution s;
    vector<vector<int>> grid = {{4, 3, 2, -1}, {3, 2, 1, -1}, {1, 1, -1, -2}, {-1, -1, -2, -3}};
    cout << s.countNegatives_3(grid) << endl;
    return 0;
}